module sorted_order_test
    use double_precision_array_generator_m, only: DOUBLE_PRECISION_ARRAY_GENERATOR
    use double_precision_array_input_m, only: double_precision_array_input_t
    use sortff, only: sorted_order
    use veggies, only: &
            input_t, &
            result_t, &
            test_item_t, &
            assert_equals, &
            assert_that, &
            describe, &
            fail, &
            it

    implicit none
    private
    public :: test_sorted_order
contains
    function test_sorted_order() result(tests)
        type(test_item_t) :: tests

        tests = describe( &
            "sorted_order", &
            [ it("returns an empty array given an empty array", check_empty) &
            , it("returns the array [1] given a single element array", check_single) &
            , it( &
                "returns the arrays [1, 2] and [2, 1] for sorted and unsorted 2 element arrays respectively", &
                check_doubles) &
            , it("is stable for 2 element arrays, in that it returns [1, 2] for an array with equal values", &
                check_stable_2_element) &
            , it( &
                "properly sorts the permutations of a 3 element array", &
                check_triples) &
            , it("is stable for longer arrays", check_stable_longer) &
            , it( &
                "returns an array the same size as the input", &
                DOUBLE_PRECISION_ARRAY_GENERATOR, &
                check_output_size) &
            , it( &
                "can be used to produce a sorted array", &
                DOUBLE_PRECISION_ARRAY_GENERATOR, &
                check_is_sorted) &
            , it( &
                "doesn't reorder a sorted array", &
                DOUBLE_PRECISION_ARRAY_GENERATOR, &
                check_idempotent) &
            ])
    end function

    function check_empty() result(result_)
        type(result_t) :: result_

        result_ = assert_equals([integer::], sorted_order([real::]))
    end function

    function check_single() result(result_)
        type(result_t) :: result_

        result_ = assert_equals([1], sorted_order([1.0]))
    end function

    function check_doubles() result(result_)
        type(result_t) :: result_

        result_ = &
                assert_equals([1, 2], sorted_order([1.0, 2.0])) &
                .and.assert_equals([2, 1], sorted_order([2.0, 1.0]))
    end function

    function check_stable_2_element() result(result_)
        type(result_t) :: result_

        result_ = assert_equals([1, 2], sorted_order([1.0, 1.0]))
    end function

    function check_triples() result(result_)
        type(result_t) :: result_

        result_ = &
                assert_equals([1, 2, 3], sorted_order([1.0, 2.0, 3.0])) &
                .and.assert_equals([1, 3, 2], sorted_order([1.0, 3.0, 2.0])) &
                .and.assert_equals([2, 1, 3], sorted_order([2.0, 1.0, 3.0])) &
                .and.assert_equals([3, 1, 2], sorted_order([2.0, 3.0, 1.0])) &
                .and.assert_equals([2, 3, 1], sorted_order([3.0, 1.0, 2.0])) &
                .and.assert_equals([3, 2, 1], sorted_order([3.0, 2.0, 1.0]))
    end function

    function check_stable_longer() result(result_)
        type(result_t) :: result_

        result_ = &
                assert_equals([1, 2, 3, 4], sorted_order([1.0, 1.0, 2.0, 3.0])) &
                .and.assert_equals([1, 2, 3, 4], sorted_order([1.0, 2.0, 2.0, 3.0])) &
                .and.assert_equals([1, 2, 3, 4], sorted_order([1.0, 2.0, 3.0, 3.0])) &
                .and.assert_equals([1, 2, 4, 3], sorted_order([1.0, 1.0, 3.0, 2.0])) &
                .and.assert_equals([1, 4, 2, 3], sorted_order([1.0, 3.0, 3.0, 2.0])) &
                .and.assert_equals([1, 3, 4, 2], sorted_order([1.0, 3.0, 2.0, 2.0])) &
                .and.assert_equals([3, 1, 2, 4], sorted_order([2.0, 2.0, 1.0, 3.0])) &
                .and.assert_equals([2, 3, 1, 4], sorted_order([2.0, 1.0, 1.0, 3.0])) &
                .and.assert_equals([2, 1, 3, 4], sorted_order([2.0, 1.0, 3.0, 3.0])) &
                .and.assert_equals([4, 1, 2, 3], sorted_order([2.0, 2.0, 3.0, 1.0])) &
                .and.assert_equals([4, 1, 2, 3], sorted_order([2.0, 3.0, 3.0, 1.0])) &
                .and.assert_equals([3, 4, 1, 2], sorted_order([2.0, 3.0, 1.0, 1.0])) &
                .and.assert_equals([3, 4, 1, 2], sorted_order([3.0, 3.0, 1.0, 2.0])) &
                .and.assert_equals([2, 3, 4, 1], sorted_order([3.0, 1.0, 1.0, 2.0])) &
                .and.assert_equals([2, 3, 4, 1], sorted_order([3.0, 1.0, 2.0, 2.0])) &
                .and.assert_equals([4, 3, 1, 2], sorted_order([3.0, 3.0, 2.0, 1.0])) &
                .and.assert_equals([4, 2, 3, 1], sorted_order([3.0, 2.0, 2.0, 1.0])) &
                .and.assert_equals([3, 4, 2, 1], sorted_order([3.0, 2.0, 1.0, 1.0]))
    end function

    function check_output_size(input) result(result_)
        class(input_t), intent(in) :: input
        type(result_t) :: result_

        double precision, allocatable :: the_array(:)

        select type (input)
        type is (double_precision_array_input_t)
            allocate(the_array, source = input%input())
            result_ = assert_equals(size(the_array), size(sorted_order(the_array)))
        class default
            result_ = fail("Expected a double_precision_array_input_t")
        end select
    end function

    function check_is_sorted(input) result(result_)
        class(input_t), intent(in) :: input
        type(result_t) :: result_

        double precision, allocatable :: the_array(:)

        select type (input)
        type is (double_precision_array_input_t)
            allocate(the_array, source = input%input())
            result_ = assert_that(is_sorted(the_array(sorted_order(the_array))))
        class default
            result_ = fail("Expected a double_precision_array_input_t")
        end select
    end function

    function check_idempotent(input) result(result_)
        class(input_t), intent(in) :: input
        type(result_t) :: result_

        integer :: i
        double precision, allocatable :: the_array(:)

        select type (input)
        type is (double_precision_array_input_t)
            allocate(the_array, source = input%input())
            result_ = assert_equals( &
                    [(i, i = 1, size(the_array))], &
                    sorted_order(the_array(sorted_order(the_array))))
        class default
            result_ = fail("Expected a double_precision_array_input_t")
        end select
    end function

    pure function is_sorted(array)
        double precision, intent(in) :: array(:)
        logical :: is_sorted

        integer :: i

        is_sorted = all([(array(i-1) <= array(i), i = 2, size(array))])
    end function
end module
